/**
 * https://leetcode.cn/submissions/detail/582421909/
 * 1971. 寻找图中是否存在路径
 * Easy, 黄伟杰 2024.11.22
 * 并查集
 */
// 并查集 1
class union_find
{
public:
    // 构造从 0 到 n - 1 的节点
    union_find(int n) : n(n)
    {
        parent = new int[n];
        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
        }
    }
    // 合并两个节点
    void pair(int index1, int index2)
    {
        parent[find(index2)] = find(index1);
    }
    // 找到根节点
    int find(int index)
    { // 递归函数，找根节点的同时进行路径压缩
        if (parent[index] != index)
        {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
    // 判断连接性
    bool check(int index1, int index2)
    {
        return find(index1) == find(index2);
    }
    // 返回连通图的数量
    int groupCount()
    { // 集合去重得到连通图的数量
        unordered_set<int> us;
        for (int i = 0; i < n; ++i)
            us.emplace(find(i));
        return us.size();
    }

private:
    int *parent, n;
};
class Solution
{
public:
    bool validPath(int n, vector<vector<int>> &edges, int source, int destination)
    {
        union_find x(n);

        for (auto &e : edges)
        {
            x.pair(e[0], e[1]);
        }
        return x.check(source, destination);
    }
};